{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Amount of New Area Painted Each Day"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #segment-tree #array #ordered-set"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #线段树 #数组 #有序集合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: amountPainted"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #每天绘制新区域的数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一幅细长的画，可以用数轴来表示。 给你一个长度为 <code>n</code> 、下标从 <strong>0</strong> 开始的二维整数数组 <code>paint</code> ，其中 <code>paint[i] = [start<sub>i</sub>, end<sub>i</sub>]</code> 表示在第 <code>i</code> 天你需要绘制 <code>start<sub>i</sub></code>&nbsp;和 <code>end<sub>i</sub></code>&nbsp;之间的区域。</p>\n",
    "\n",
    "<p>多次绘制同一区域会导致不均匀，因此每个区域最多只能绘制 <strong>一次 </strong>。</p>\n",
    "\n",
    "<p>返回一个长度为 <code>n</code> 的整数数组 <code>worklog</code>，其中 <code>worklog[i]</code> 是你在第 <code>i</code> 天绘制的<strong> 新 </strong>区域的数量。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/02/01/screenshot-2022-02-01-at-17-16-16-diagram-drawio-diagrams-net.png\" style=\"height: 300px; width: 620px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>paint = [[1,4],[4,7],[5,8]]\n",
    "<strong>输出：</strong>[3,3,1]\n",
    "<strong>解释：\n",
    "</strong>在第 0 天，绘制 1 到 4 之间的所有内容。\n",
    "第 0 天绘制的新区域数量为 4 - 1 = 3 。\n",
    "在第 1 天，绘制 4 到 7 之间的所有内容。\n",
    "第 1 天绘制的新区域数量为 7 - 4 = 3 。\n",
    "在第 2 天，绘制 7 到 8 之间的所有内容。\n",
    "5 到 7 之间的所有内容都已在第 1 天绘制完毕。\n",
    "第 2 天绘制的新区域数量为 8 - 7 = 1 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/02/01/screenshot-2022-02-01-at-17-17-45-diagram-drawio-diagrams-net.png\" style=\"width: 604px; height: 300px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>paint = [[1,4],[5,8],[4,7]]\n",
    "<strong>输出：</strong>[3,3,1]\n",
    "<strong>解释：</strong>\n",
    "在第 0 天，绘制 1 到 4 之间的所有内容。\n",
    "第 0 天绘制的新区域数量为 4 - 1 = 3 。\n",
    "第 1 天，绘制 5 到 8 之间的所有内容。\n",
    "第 1 天绘制的新区域数量为 8 - 5 = 3 。\n",
    "在第 2 天，绘制 4 到 5 之间的所有内容。\n",
    "5 到 7 之间的所有内容都已在第 1 天绘制完毕。\n",
    "第 2 天绘制的新区域数量为 5 - 4 = 1 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;3：</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/02/01/screenshot-2022-02-01-at-17-19-49-diagram-drawio-diagrams-net.png\" style=\"width: 423px; height: 275px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>paint = [[1,5],[2,4]]\n",
    "<strong>输出：</strong>[4,0]\n",
    "<strong>解释：</strong>\n",
    "在第 0 天，绘制 1 到 5 之间的所有内容。\n",
    "第 0 天绘制的新区域数量为 5 - 1 = 4 。\n",
    "在第 1 天，什么都不画，因为第 0 天已经画了 2 到 4 之间的所有内容。\n",
    "第 1 天绘制的新区域数量为 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= paint.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>paint[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= start<sub>i</sub> &lt; end<sub>i</sub> &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [amount-of-new-area-painted-each-day](https://leetcode.cn/problems/amount-of-new-area-painted-each-day/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [amount-of-new-area-painted-each-day](https://leetcode.cn/problems/amount-of-new-area-painted-each-day/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,4],[4,7],[5,8]]', '[[1,4],[5,8],[4,7]]', '[[1,5],[2,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def amountPainted(self, paint: List[List[int]]) -> List[int]:\n",
    "        uf = UnionFindRange2(int(5e4) + 10)\n",
    "        return [uf.unionRange(start, end + 1) for start, end in paint]\n",
    "\n",
    "\n",
    "class UnionFindRange2:\n",
    "    \"\"\"\n",
    "    维护每个分组左右边界的区间并查集.\n",
    "    按秩合并.\n",
    "    \"\"\"\n",
    "\n",
    "    ___slots___ = (\"groupStart\", \"groupEnd\", \"part\", \"_n\", \"_data\")\n",
    "\n",
    "    def __init__(self, n: int):\n",
    "        self.groupStart = list(range(n))  # 每个组的左边界,包含端点\n",
    "        self.groupEnd = [i + 1 for i in range(n)]  # 每个组的右边界,不包含端点\n",
    "        self.part = n\n",
    "        self._n = n\n",
    "        self._data = [-1] * n\n",
    "\n",
    "    def unionRange(self, start: int, end: int) -> int:\n",
    "        \"\"\"合并[start,end)左闭右开区间, 返回合并次数.\n",
    "        0<=groupStart<=groupEnd<=n.\n",
    "        \"\"\"\n",
    "        if start < 0:\n",
    "            start = 0\n",
    "        if end > self._n:\n",
    "            end = self._n\n",
    "        if start >= end:\n",
    "            return 0\n",
    "        count = 0\n",
    "        while True:\n",
    "            next_ = self.groupEnd[self.find(start)]\n",
    "            if next_ >= end:\n",
    "                break\n",
    "            self.union(start, next_)\n",
    "            count += 1\n",
    "        return count\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        if self._data[x] < 0:\n",
    "            return x\n",
    "        self._data[x] = self.find(self._data[x])\n",
    "        return self._data[x]\n",
    "\n",
    "    def union(self, x: int, y: int) -> bool:\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX == rootY:\n",
    "            return False\n",
    "        if self._data[rootX] > self._data[rootY]:\n",
    "            rootX, rootY = rootY, rootX\n",
    "        self._data[rootX] += self._data[rootY]\n",
    "        self._data[rootY] = rootX\n",
    "        if self.groupStart[rootY] < self.groupStart[rootX]:\n",
    "            self.groupStart[rootX] = self.groupStart[rootY]\n",
    "        if self.groupEnd[rootY] > self.groupEnd[rootX]:\n",
    "            self.groupEnd[rootX] = self.groupEnd[rootY]\n",
    "        return True\n",
    "\n",
    "    def isConnected(self, x: int, y: int) -> bool:\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def getSize(self, x: int) -> int:\n",
    "        return -self._data[self.find(x)]\n",
    "\n",
    "    def getRange(self, x: int) -> Tuple[int, int]:\n",
    "        \"\"\"每个点所在的组的左右边界[左边界,右边界).\"\"\"\n",
    "        root = self.find(x)\n",
    "        return self.groupStart[root], self.groupEnd[root]\n",
    "\n",
    "    def getGroups(self) -> \"DefaultDict[int, List[int]]\":\n",
    "        group = defaultdict(list)\n",
    "        for i in range(self._n):\n",
    "            group[self.find(i)].append(i)\n",
    "        return group"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def amountPainted(self, paint: List[List[int]]) -> List[int]:\n",
    "        seen = {}\n",
    "        work_log = []\n",
    "\n",
    "        for start, end in paint:\n",
    "            work = 0\n",
    "\n",
    "            while start < end:\n",
    "                if start in seen:\n",
    "                    jump = seen[start]\n",
    "                    seen[start] = max(end, jump) \n",
    "                    start = jump\n",
    "                else:\n",
    "                    seen[start] = end\n",
    "                    work += 1\n",
    "                    start += 1\n",
    "\n",
    "            work_log.append(work)\n",
    "\n",
    "        return work_log\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def amountPainted(self, paint: List[List[int]]) -> List[int]:\n",
    "        worklog = []\n",
    "        painted = {}\n",
    "\n",
    "        for s, e in paint:\n",
    "            if s in painted and painted[s] >= e:\n",
    "                worklog.append(0)\n",
    "                continue\n",
    "            cnt = 0\n",
    "            \n",
    "            while s < e:\n",
    "                if s in painted:\n",
    "                    jump = painted[s]\n",
    "                    painted[s] = max(e, jump)\n",
    "                    s = jump\n",
    "                else:\n",
    "                    painted[s] = e\n",
    "                    cnt += 1\n",
    "                    s += 1\n",
    "\n",
    "            worklog.append(cnt)\n",
    "        \n",
    "        return worklog"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class UnionSet:\n",
    "        def __init__(self, n):\n",
    "            self.parent = list(range(n))\n",
    "        \n",
    "        def find(self, x):\n",
    "            while x != self.parent[x]:\n",
    "                self.parent[x] = self.parent[self.parent[x]]\n",
    "                x = self.parent[x]\n",
    "            return x\n",
    "        \n",
    "        def union(self, x, y):\n",
    "            x0 = self.find(x)\n",
    "            y0 = self.find(y)\n",
    "            if x0 == y0:\n",
    "                return x0\n",
    "            if x0 > y0:\n",
    "                x0, y0 = y0, x0\n",
    "            self.parent[y0] = x0\n",
    "            return x0\n",
    "\n",
    "    def amountPainted(self, paint: List[List[int]]) -> List[int]:\n",
    "        us = self.UnionSet(50003)\n",
    "        works = []\n",
    "        for l, r in paint:\n",
    "            work = 0\n",
    "            l = us.find(l)\n",
    "            r = us.find(r)\n",
    "            while r > l:\n",
    "                work += 1\n",
    "                r = us.union(r, r - 1)\n",
    "            works.append(work)\n",
    "        return works\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def amountPainted(self, paint: List[List[int]]) -> List[int]:\n",
    "        cover = list(range(50003))\n",
    "        works = []\n",
    "        for l, r in paint:\n",
    "            work = 0\n",
    "            while l < r:\n",
    "                while l != cover[l]:\n",
    "                    cover[l] = cover[cover[l]]\n",
    "                    l = cover[l]\n",
    "                if l < r:\n",
    "                    cover[l] = r\n",
    "                    work += 1\n",
    "                    l += 1\n",
    "            works.append(work)\n",
    "        return works"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def amountPainted(self, paint: List[List[int]]) -> List[int]:\n",
    "\n",
    "        records = []\n",
    "        res = []\n",
    "\n",
    "        for item in paint:\n",
    "            new_record = [item[0], item[1]]\n",
    "            origin_len = 0\n",
    "            remove_list = []\n",
    "            for record in records:\n",
    "                if (new_record[0] <= record[0] <= new_record[1]) \\\n",
    "                        or (new_record[0] <= record[1] <= new_record[1]) \\\n",
    "                        or (record[0] <= new_record[0] and new_record[1] <= record[1]):\n",
    "                    new_record = [min(record[0], new_record[0]), max(record[1], new_record[1])]\n",
    "                    origin_len = origin_len + record[1] - record[0]\n",
    "                    remove_list.append(record)\n",
    "            for x in remove_list:\n",
    "                records.remove(x)\n",
    "            records.append(new_record)\n",
    "            res.append(new_record[1] - new_record[0] - origin_len)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class UnionSet:\n",
    "        def __init__(self, n):\n",
    "            self.parent = list(range(n))\n",
    "        \n",
    "        def find(self, x):\n",
    "            while self.parent[x] != x:\n",
    "                self.parent[x] = self.parent[self.parent[x]]\n",
    "                x = self.parent[x]\n",
    "            return x\n",
    "\n",
    "        def union(self, x, y):\n",
    "            x_root = self.find(x)\n",
    "            y_root = self.find(y)\n",
    "            if x_root < y_root:\n",
    "                self.parent[x_root] = y_root\n",
    "                # print(f\"union_root: {y_root}\")\n",
    "                return y_root\n",
    "            elif x_root > y_root:\n",
    "                self.parent[y_root] = x_root\n",
    "                # print(f\"union_root: {x_root}\")\n",
    "                return x_root\n",
    "            # print(f\"union_root: {x_root}\")\n",
    "            return x_root\n",
    "\n",
    "    def amountPainted(self, paint: List[List[int]]) -> List[int]:\n",
    "        us = self.UnionSet(50003)\n",
    "        worklog = []\n",
    "        for start, end in paint:\n",
    "            start_root = us.find(start)\n",
    "            end_root = us.find(end)\n",
    "            steps = 0\n",
    "            while start_root != end_root:\n",
    "                start_root = us.union(start_root, start_root + 1)\n",
    "                print(steps)\n",
    "                steps +=1\n",
    "            worklog.append(steps)\n",
    "        return worklog"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.pa = list(range(50010))\n",
    "        self.n = 0\n",
    "\n",
    "    def find(self, x):\n",
    "        if x == self.pa[x]:\n",
    "            return x\n",
    "        else:\n",
    "            self.pa[x] = self.find(self.pa[x])\n",
    "            return self.pa[x]\n",
    "\n",
    "    def amountPainted(self, paint):\n",
    "        self.n = len(paint)\n",
    "        res = [0] * self.n\n",
    "\n",
    "        for i in range(self.n):\n",
    "            cnt = 0\n",
    "            a, b = paint[i][0], paint[i][1]\n",
    "            a, b = self.find(a), self.find(b)\n",
    "\n",
    "            while b != a:  # Continue until b is connected to a\n",
    "                self.pa[b] = self.find(b - 1)\n",
    "                cnt += 1\n",
    "                b = self.find(b)\n",
    "\n",
    "            res[i] = cnt\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class UnionFindArray:\n",
    "    def __init__(self, n: int):\n",
    "        self.n = n\n",
    "        self.count = n\n",
    "        self.parent = list(range(n))\n",
    "        self.rank = [1] * n\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        if x != self.parent[x]:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, x: int, y: int) -> bool:\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX == rootY:\n",
    "            return False\n",
    "\n",
    "        # 大的总是指向小的\n",
    "        rootX, rootY = sorted([rootX, rootY])\n",
    "        self.parent[rootY] = rootX\n",
    "        self.rank[rootX] += self.rank[rootY]\n",
    "        self.count -= 1\n",
    "        return True\n",
    "\n",
    "    def isConnected(self, x: int, y: int) -> bool:\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def amountPainted(self, paint: List[List[int]]) -> List[int]:\n",
    "        uf = UnionFindArray(int(5e4) + 10)\n",
    "        res = []\n",
    "        for start, end in paint:\n",
    "            startRoot = uf.find(start)\n",
    "            endRoot = uf.find(end)\n",
    "            cur = 0\n",
    "            while endRoot != startRoot:\n",
    "                cur += 1\n",
    "                uf.union(endRoot, endRoot - 1)\n",
    "                endRoot = uf.find(endRoot)\n",
    "            res.append(cur)\n",
    "\n",
    "        return res\n",
    "\n",
    "# 作者：草莓奶昔\\U0001f353\n",
    "# 链接：https://leetcode.cn/problems/amount-of-new-area-painted-each-day/solutions/1264208/qu-jian-bing-cha-ji-by-981377660lmt-p1zl/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class UnionFindArray:\n",
    "    def __init__(self, n: int):\n",
    "        self.n = n\n",
    "        self.count = n\n",
    "        self.parent = list(range(n))\n",
    "        self.rank = [1] * n\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        if x != self.parent[x]:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, x: int, y: int) -> bool:\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX == rootY:\n",
    "            return False\n",
    "\n",
    "        # 大的总是指向小的\n",
    "        rootX, rootY = sorted([rootX, rootY])\n",
    "        self.parent[rootY] = rootX\n",
    "        self.rank[rootX] += self.rank[rootY]\n",
    "        self.count -= 1\n",
    "        return True\n",
    "\n",
    "    def isConnected(self, x: int, y: int) -> bool:\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def amountPainted(self, paint: List[List[int]]) -> List[int]:\n",
    "        uf = UnionFindArray(int(5e4) + 10)\n",
    "        res = []\n",
    "        for start, end in paint:\n",
    "            startRoot = uf.find(start)\n",
    "            endRoot = uf.find(end)\n",
    "            cur = 0\n",
    "            while endRoot != startRoot:\n",
    "                cur += 1\n",
    "                uf.union(endRoot, endRoot - 1)\n",
    "                endRoot = uf.find(endRoot)\n",
    "            res.append(cur)\n",
    "\n",
    "        return res\n",
    "\n",
    "# 作者：草莓奶昔\\U0001f353\n",
    "# 链接：https://leetcode.cn/problems/amount-of-new-area-painted-each-day/solutions/1264208/qu-jian-bing-cha-ji-by-981377660lmt-p1zl/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def amountPainted(self, paint: List[List[int]]) -> List[int]:\n",
    "        endpoints = []\n",
    "        ans = [0] * len(paint)\n",
    "        for i, (s, e) in enumerate(paint):\n",
    "            endpoints.append((s, i, 1))\n",
    "            endpoints.append((e, i, 0))\n",
    "        endpoints.sort()\n",
    "        active = []\n",
    "        remove = set()\n",
    "        last_x = -1\n",
    "        for x, i, t in endpoints:\n",
    "            if active:\n",
    "                ans[active[0]] += x - last_x\n",
    "            last_x = x\n",
    "            if t:\n",
    "                heapq.heappush(active, i)\n",
    "            else:\n",
    "                remove.add(i)\n",
    "                while len(active) > 0 and active[0] in remove:\n",
    "                    heapq.heappop(active)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def amountPainted(self, paint: List[List[int]]) -> List[int]:\n",
    "        endpoints = []\n",
    "        ans = [0] * len(paint)\n",
    "        for i, (s, e) in enumerate(paint):\n",
    "            endpoints.append((s, i, 1))\n",
    "            endpoints.append((e, i, 0))\n",
    "        endpoints.sort()\n",
    "        active = []\n",
    "        remove = set()\n",
    "        last_x = -1\n",
    "        for x, i, t in endpoints:\n",
    "            if active:\n",
    "                ans[active[0]] += x - last_x\n",
    "            last_x = x\n",
    "            if t:\n",
    "                heapq.heappush(active, i)\n",
    "            else:\n",
    "                remove.add(i)\n",
    "                while len(active) > 0 and active[0] in remove:\n",
    "                    heapq.heappop(active)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def amountPainted(self, paint: List[List[int]]) -> List[int]:\n",
    "        f = {}\n",
    "\n",
    "        def find(x):\n",
    "            f.setdefault(x, x)\n",
    "            if f[x] != x:\n",
    "                f[x] = find(f[x])\n",
    "            return f[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            f[find(x)] = find(y)\n",
    "\n",
    "        def connected(x, y):\n",
    "            return find(x) == find(y)\n",
    "        ans = []\n",
    "        for start, end in paint:\n",
    "            start_root = find(start)\n",
    "            end_root = find(end)\n",
    "            count = 0\n",
    "\n",
    "            while end_root != start_root:\n",
    "                count += 1\n",
    "                union(end_root, end_root - 1)\n",
    "                end_root = find(end_root)\n",
    "            ans.append(count)\n",
    "\n",
    "        return ans\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def amountPainted(self, paint: List[List[int]]) -> List[int]:\n",
    "        n = len(bin(max(i[1] for i in paint)))-2\n",
    "        has, ans = [[0,0,0]], []\n",
    "        N = 1 << n\n",
    "        m = 1 << n\n",
    "        while m:\n",
    "            has += [[m, i * m, (i+1) * m]  for i in range(N//m)]\n",
    "            m >>= 1\n",
    "        def dfs(x):\n",
    "            if has[x][1] >= r or has[x][2] <= l: return 0\n",
    "            if x >= N or not has[x][0]: tep = has[x][0]\n",
    "            else: tep = dfs(2*x) + dfs(2*x+1)\n",
    "            has[x][0] -= tep\n",
    "            return tep\n",
    "\n",
    "        \n",
    "        for l, r in paint:\n",
    "            ans.append(dfs(1))\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def amountPainted(self, paint: List[List[int]]) -> List[int]:\n",
    "        f = {}\n",
    "\n",
    "        def find(x):\n",
    "            f.setdefault(x, x)\n",
    "            if f[x] != x:\n",
    "                f[x] = find(f[x])\n",
    "            return f[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            f[find(x)] = find(y)\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        for start, end in paint:\n",
    "            start_root = find(start)\n",
    "            end_root = find(end)\n",
    "            count = 0\n",
    "\n",
    "            while start_root != end_root:\n",
    "                count += 1\n",
    "                union(start_root, start_root + 1)\n",
    "                start_root = find(start_root)\n",
    "            ans.append(count)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def amountPainted(self, paint: List[List[int]]) -> List[int]:\n",
    "        def find(x):\n",
    "            if f[x]!=x:\n",
    "                f[x] = find(f[x])\n",
    "            return f[x]\n",
    "\n",
    "        def union(x,y):\n",
    "            f[find(x)] = find(y)\n",
    "\n",
    "        m = max(b for a,b in paint)\n",
    "        f = list(range(m+1))\n",
    "        res = []\n",
    "        for a,b in paint:\n",
    "            x,w = find(a),0\n",
    "            while x<b:\n",
    "                w += 1\n",
    "                union(x,x+1)\n",
    "                x = find(x)\n",
    "            res.append(w)\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
